package pers.qianyu.month_202102.date_20210208;

import org.junit.*;
import pers.qianyu.util.*;
import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 971. 翻转二叉树以匹配先序遍历
 * https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal/
 *
 * @author mizzle rain
 * @date 2021-02-08 20:36
 */
public class FlipMatchVoyage {
    private int[] voyage;
    private List<Integer> res = new ArrayList<>();
    private int cur = 0;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        recur(root);
        if (!res.isEmpty() && res.get(0) == -1) {
            res.clear();
            res.add(-1);
        }
        return res;
    }

    private void recur(TreeNode root) {
        if (root == null || cur >= voyage.length) return;
        if (root.val != voyage[cur++]) {
            res.clear();
            res.add(-1);
            return;
        }
        if (cur < voyage.length && root.left != null && root.left.val != voyage[cur]) {
            res.add(root.val);
            recur(root.right);
            recur(root.left);
        } else {
            recur(root.left);
            recur(root.right);
        }
    }

    @Test
    public void test1() {
        TreeNode root = BinTreeUtil.generateBinTree(new Integer[]{1, 2, 3});
        List<Integer> result = new FlipMatchVoyage().flipMatchVoyage(root, new int[]{1, 3, 2});
        List<Integer> expect = new ArrayList<>();
        expect.add(1);
        Assert.assertEquals(expect, result);
    }
}
